The present invention relates to a data processing apparatus and a data processing method, and more particularly, to data processing by a semiconductor intergrated circuit, above all, to data processing employing associative memory.
In recent years, along with provision of multi-function and higher function of household electrical goods or the like, adaptation of computer technology to household products is rapidly advanced, whereby a virtual storage control unit which was conventionally employed for mainly high-grade workstations, personal computers, or the like is being adopted to operation systems (OS), which cope with the processing of a plurality of task processing also in household equipment such as a Set-Top Box, as an apparatus for connecting CATV or Internet to a television receiver.
The virtual storage control unit is technology employed for effectively utilizing a high speed semiconductor memory that is used as a main memory in a computer, and the virtual storage control unit employs an external storage device such as a hard disk that has generally low speed but has a large capacity as a substitute for a memory. By the use of the virtual storage control unit, even when a capacity of actually installed main memory is small, it is possible to drive software which requires a large capacity memory for its execution, or to deal with a large quantity of data speedily.
In order to realize this, when it comes to a state where there is no empty region in the main memory, a part of the content stored in the main memory is written into the external storage device, and it is read out therefrom when it is needed. In the virtual storage control unit, a logical address space which is larger than physical memory capacity is to be realized. The logical address space is called as a logical space while the physical memory space is called as a physical space. Since the position of the logical space is specified by a logical address and the position on the physical space is specified by a physical address, it is required in a data processing apparatus to provide a mechanism for performing translation between the logical address and the physical address so as to perform virtual storage management.
Generally, while in a computer system a plurality of tasks (a task is a unit of a work which a computer performs) are performed it reduces the processing speed to perform writing/reading of all the content concerning a task stored in a main memory every time the task is changed. Accordingly, a logical task space is divided into pages in unit, and mapping, i.e., making correspondence between a logical space and a physical space is carried out in unit of page, thereby enhancing the efficiency.
In the address translation processing, a search is performed with providing a translation table (page table) showing the correspondence relation in the external memory (main memory device or the like) and the OS referring to the translation table when it is needed. However, because a processing load for such processing is large, there are many cases where the processing speed of the data processing apparatus is decreased due to employing the virtual storage control unit. Accordingly, an address translation buffer (Translation Look-aside Buffer; hereinafter recited xe2x80x9cTLBxe2x80x9d) which stores pairs of logical address and physical address in frequent use in a high speed memory, i.e., which cashes the same is employed, in order to realize a high speed address translation processing. The TLB may be often constituted as an associative storage device in which when an item is input as a key item an associative item in an associative relation therewith is obtained.
Generally, a cash memory comprises a data area for keeping data itself and a tag area for holding an address indicating a data storage position, or an access history, and the like. Either of the areas is managed divided into a plurality of blocks. The block constituting the data area is called as a line, and inputting/outputting of data in the cash memory is performed in line unit.
As a method for making correspondence between the data on the main memory such as the translation table with the line of the cash memory, there are a set-associative method, a direct-mapping method, and a full-associative method. The set-associative method is a method in which the cash memory and the main memory are divided into plural sets (a set is a collection of lines), and the data on the main memory can only be stored in the prescribed line in each set. When the number of sets is n, it is called n-way-set-associative method. The direct-mapping method corresponds to 1-way-set-associative method wherein the whole cash memory is dealt as one set. On the other hand, a method in which data is stored in an arbitrary line is a full-associative method.
With respect to these methods, considering the rate of making a hit with the cash, the direct-mapping method which has a strong possibility that a replacement occurs has many error hits and the low hit rate, while the full-associative method has the high hit rate by comparison. Besides, in the set-associative method, the hit rate is between those of the both methods. Generally, for the management of the cash memory the set-associative method is employed; however, in case of TLB, the adoption of the full-associative method which has the high hit rate is preferable as an adverse effect on the lowering of the processing efficiency due to the error hits is enormous.
As described above, at the time of changing tasks, content of the cash memory including the TLB is updated. Hereinafter, a TLB managing method at the time of the updating according to a prior art disclosed in Japanese Published Patent Application No. Hei. 8-320829 will be described. At the updating, the nullification processing of a TLB entry is required. In the prior art, at the nullification processing of an entry concerning the specified page, a search is performed specifying a way of the TLB that was IO-mapped employing MOV instruction.
In the nullification processing of the specified entry according to the prior art, provided that a mapping address of each way of the TLB is 0xfn000000 (n=0xe2x88x927), and logical page number is 0xbeef0, the processing can be realized with the following program.
1) MOV xe2x80x9c0xbeef0000xe2x80x9d R0
2) MOV xe2x80x9c0xf0000080xe2x80x9d R1
3) MOV xe2x80x9c0x01000000xe2x80x9d R2
4) MOV R0, (R1)
5) ADD R2, R1
At 1), the logical page number to search (0xbeef0) and valid flag (0=invalid) are set to R0, and at 2), a mapping address (0xf0) and a flag (0x80) for making a comparison are set to R1, then at 3), an offset of the mapping address of each way (0x01000000) is set to R2. At 4), writing of the content of R0 (0xbeef0000) to the address indicated by R1 (0xf0000080) is performed, and in case where the result of the comparison of the logical page number matches, the content of R0 (0xbeef0000) is written into the that way of the TLB, while in case of making no hit, writing is not performed. At 5), the offset is added to the mapping address, thereby to create a mapping address of the next way, and the processing returns to 4), and such processing is repeated as many times as the number of the ways of the TLB.
As described above, in the TLB management according to the prior art, the content of TLB entry is searched for each way. Accordingly, the number of steps until the nullification processing is completed depends on the number of ways, that is, in case where the number of way is 1, the above-described 5 steps, 1)-5), are required, and in case where the number of way is n, 2n+2 steps are required. In the above-mentioned Japanese Published Patent Application No. Hei. 8-320829, the case of set-associative method of 2 ways or 4 ways is disclosed. In such a case where the number of ways is not very high, there is no problem in the aspect of the processing efficiency or the like; however, as the number of ways becomes high, the number of required steps is increased, whereby the time required for the processing is also increased. As described above, in case of the TLB which employs the full-associative method, the entry numbers and the way number are equal to each other, thereby resulting in a problem that the processing time is increased in proportion to the way number.
The present invention is made to solve the above-mentioned problem and has for its object to provide a data processing apparatus and a data processing method which can perform the searching processing of an associative memory such as TLB speedily.
To achieve the above-mentioned object, a data processing apparatus according to Claim 1 of the present invention is one which, employing an associative storage device which performs associative processing by storing plural pairs of first information and second information and outputs, when the specified first information is input, a second information making a pair with the specified first information, comprises: first information holding means for holding the first information; second information holding means for holding the second information; associative information control means for performing a control to execute the associative processing by inputting the first information held in the first information holding means to the associative storage device, and to hold the second information which makes a pair with the input first information and which is output as the result of the associative processing by the second information holding means when the input first information matches one among the first information stored in the associative storage device; information pair specifying information holding means for holding information which specifies a pair among pairs of the information stored in the associative storage device; and central processing unit for controlling the data processing employing the associative storage device, and the above-mentioned associative information control means of the apparatus, in response to reading out of information held by the second information holding means, by the central processing unit, performs a control to execute the associative processing by inputting the first information held in the first information holding means to the associative storage device, and to hold the second information which makes a pair with the input first information and which is output as the result of the associative processing in the second information holding means when the input first information matches one among the first information stored in the associative storage device, as well as to hold the information which specifies a pair of the matched first information and the second information in the information pair specifying information holding means, and the above-mentioned first information holding means and the above-mentioned second information holding means of the apparatus are allocated in the address space administrated by the central processing unit, and inputting/outputting of information is performed by designating information which specifies the allocation position in the address space.
According to the invention described in Claim 5, the data processing apparatus is the one which, employing an associative storage device which performs associative processing by storing plural pairs of first information and second information and outputs, when the specified first information is input, a second information making a pair with the specified first information, comprises: first information holding means for holding the first information; second information holding means for holding the second information; associative information control means for performing a control to execute the associative processing by inputting the first information held in the first information holding means to the associative storage device, and to hold the second information which makes a pair with the input first information which is output as the result of the associative processing in the second information holding means when the input first information matches one among the first information stored in the associative storage device; information pair specifying information holding means for holding information which specifies a pair among pairs of the information stored in the associative storage device; and central processing unit for controlling the data processing employing the associative storage device, and the above-described information control means of the apparatus, it response to writing of information output by the central processing unit to the second information holding means, performs a control to write the information held in the first information holding means and the information held in the second information holding means to one of the pairs in the associative storage device indicated by the information pair specifying information holding means, and the above-described first information holding meals and the above-described second information holding means are allocated in the address space administrated by the central processing unit, and inputting/outputting of information is performed by designating information which specifies the allocation position in the address space.
According to the invention described in Claim 2, in the data processing apparatus described in Claim 1 or 5, the associative storage device is an address translation table, and the first information is a logical page address while the second information is a physical page address.
According to the invention described in Claim 3, in the data processing apparatus described in Claim 1 or 5, the associative storage device is a cash memory, and the first information is an address while the second information is an instruction or data of operand.
According to the invention described in Claim 4, in the data processing apparatus described in Claim 1 or 5, the associative storage device is a branch history buffer, and the first information is an address of branch instruction while the second information is an address of branch destination instruction.
According to the invention described in Claim 9, there is provided a data processing method which, employing an associative storage device which performs associative processing by storing plural pairs of first information and second information and outputs, when the specified first information is input, a second information making a pair with the specified first information, comprises: first information holding step of holding the first information; second information holding step of holding the second information; associative processing step of making the associative processing executed by inputting the first information held in the first information holding step to the associative storage device; holding information control step of performing a control to hold the second information which makes a pair with the input first information and which is output as the result of the associative processing in the second information holdine step when the input first information matches one among the first information stored in the associative storage device; information pair specifying information holding step of holding information which specifies a pair among pairs of the information stored in the associative storage device; and central processing step of controlling the data processing employing the associative storage device, and the above-mentioned holding information control step, in response to reading out of information held in the second information holding step, in the central processing stop, performs a control to hold the information which specifies a pair of the first information matched in the associative processing step and the second information in the information pair specifying information holding step, and the above-mentioned first information holding step and the above-mentioned second information holding step of the apparatus are allocated in the address space administrated in the central processing step, and inputting/outputting of information is performed by designating the information which specifies the allocation position in the address space.
According to the invention described in Claim 10, the data processing method is the one which, employing an associative storage device which performs associative processing by storing plural pairs of first information and second information and outputs, when the specified first information is input, a second information making a pair with the specified first information, comprises: first information holding step of holding the first information; second information holding step of holding the second information; associative processing step of making the associative processing executed by inputting the first information held in the first information holding step to the associative storage device; holding information control step of performing a control to hold the second information which makes a pair with the input first information and which is output as the result of the associative processing in the second information holding step when the input first information matches one among the first information stored in the associative storage device; information pair specifying information holding step of holding information which specifies a pair among pairs of the information stored in the associative storage device; and central processing step of controlling the data processing employing the associative storage device, and the above-described holding information control step, in response to writing against the second information holding step by the central processing step, performs a control to write the information held in the first information holding step and the information held in the second information holding step to one of the pairs in the associative storage device indicated in the information pair specifying information holding step, and the above-described first information holding step and the above-describe second information holding step are allocated in the address space administrated in the central processing step, and inputting/outputting of information is performed by designating the information which specifies the allocation position in the address space.